import java.util.ArrayList;
import java.util.Collections;

/**
 * 合并两个已经排序好的链表。
 */
public class JavaDemo16 {
    public static void main(String[] args) {
        int[] arrays = {1, 3, 5,9};
        ListNode head = new ListNode(0);
        ListNode next = head;
        for (int i = 0; i < arrays.length; i++) {
            ListNode node = new ListNode(arrays[i]);
            next.next = node;
            next = node;
        }
        ListNode head1 = new ListNode(2);
        ListNode next1 = head1;
        int[] arrays1 = {4, 6, 8};
        for (int i = 0; i < arrays1.length; i++) {
            ListNode node = new ListNode(arrays1[i]);
            next1.next = node;
            next1 = node;
        }
        // 0,1,3,5，和2,4,6,8合并。
        ListNode merge = mergeNode(head, head1);
        System.out.println("-----------------");
        ListNode showParent = merge;
        while (showParent != null) {
            System.out.println(showParent.val);
            showParent = showParent.next;
        }
    }

    /**
     * 合并两个node
     *重新创建链表
     * @param head
     * @param head1
     * @return
     */
    private static ListNode mergeNode(ListNode head, ListNode head1) {
       ListNode cur= new ListNode(-1);
       ListNode newHead= cur;
       while (head!=null&&head1!=null){
           if (head.val>=head1.val){
                newHead.next=head1;
                head1=head1.next;
           }else {
                newHead.next=head;
                head=head.next;
           }

           newHead=newHead.next;
           System.out.println(newHead.val);
       }
       if (head!=null){
           newHead.next=head;
       }
       if (head1!=null){
           newHead.next=head1;
       }
        return cur.next;
    }
}
